package org.labuladong.动态规划算法.一维DP;

/**
 * 计算最长递增子序列的长度。
 * 
 * DP解法：
 * dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。
 * 
 * 动态规划方程
 * dp[i] = max(dp[j]) + 1, j < i 且 nums[j] < nums[i]
 *
 * @author Fql18
 */
public class LC_300最长递增子序列DP {

	public static int lengthOfLIS(int[] nums) {
		if (nums == null || nums.length == 0) {
			return 0;
		}

		// 初始化动态规划数组，dp[i] 表示到索引 i 结尾的最长递增子序列的长度
		int[] dp = new int[nums.length];
		// 初始化长度为1，因为每个元素本身可以构成长度为1的子序列
		for (int i = 0; i < nums.length; i++) {
			dp[i] = 1;
		}

		int maxLength = 1; // 最长递增子序列的初始长度至少为1


		for (int i = 0; i < nums.length; i++) {
			for (int j = 0; j < i; j++) {
				if(nums[i] > nums[j]){
					// dp[i] = max(dp[j]) + 1
					dp[i]= Math.max(dp[i], dp[j] + 1);
				}
			}

		}
		
		

		// 动态规划，遍历数组填充 dp 数组
		for (int i = 1; i < nums.length; i++) {
			for (int j = 0; j < i; j++) {
				if (nums[i] > nums[j]) {
					// 如果 nums[i] 可以接在 nums[j] 后面形成更长的递增子序列，则更新 dp[i]
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}
			}
			// 更新最长递增子序列的长度
			maxLength = Math.max(maxLength, dp[i]);
		}

		return maxLength;
	}

	public static void main(String[] args) {
		int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
		int length = lengthOfLIS(nums);
		System.out.println(length); // 输出应该是最长递增子序列的长度
	}
}